Search for: All records

The main focus of this article is radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the form of a budget constraint. In addition to the standard (homogeneous) setting where all clients must be within a distance\(R\)of the nearest facility, we provide results for the more general problem where the radius demands may beinhomogeneous(i.e., different for each client). We also explore a number of variants where additional constraints are imposed on the first-stage decisions, specifically matroid and multi-knapsack constraints, and provide results for these settings. We derive results for the most general distributional setting, where there is only black-box access to the underlying distribution. To accomplish this, we first develop algorithms for thepolynomial scenariossetting; we then employ a novelscenario-discardingvariant of the standardSample Average Approximationmethod, which crucially exploits properties of the restricted-case algorithms. We note that the scenario-discarding modification to the SAA method is necessary to optimize over the radius. 

We report the effect of shape anisotropy and material properties on the directed assembly of binary suspensions composed of magnetizable ellipsoids. In a Monte Carlo simulation, we implement the ellipsoid-dipole model to calculate the pairwise dipolar interaction energy as a function of position and orientation. The analysis explores dilute suspensions of paramagnetic and diamagnetic ellipsoids with different aspect ratios in a superparamagnetic medium. We analyze the local order of binary structuresas a function of particle aspect ratio, medium permeability, and dipolar interaction strength. Our results show that local order and symmetry are tunable under the influence of a uniform magnetic field when one component of the structure is dilute with respect to the other. The simulation results match previously reported experiments on the directed assembly of binary suspension of spheres. Additionally, we report the conditions on particle aspect ratios and medium properties for various structures with rotational symmetries, as well as open and enclosed structures under the influence of a uniform magnetic field. 

ABSTRACT Twitching motility is a form of bacterial surface translocation powered by the type IV pilus (T4P). It is frequently analyzed by interstitial colony expansion between agar and the polystyrene surfaces of petri dishes. In such assays, the twitching motility ofAcinetobacter nosocomialiswas observed with MacConkey but not Luria-Bertani (LB) agar media. One difference between these two media is the presence of bile salts as a selective agent in MacConkey but not in LB. Here, we demonstrate that the addition of bile salts to LB allowedA. nosocomialisto display twitching. Similarly, bile salts enhanced the twitching ofAcinetobacter baumanniiandPseudomonas aeruginosain LB. These observations suggest that there is a common mechanism, whereby bile salts enhance bacterial twitching and promote interstitial colony expansion. Bile salts disrupt lipid membranes and apply envelope stress as detergents. Surprisingly, their stimulatory effect on twitching appears not to be related to a bacterial physiological response to stressors. Rather, it is due to their ability to alter the physicochemical properties of a twitching surface. We observed that while other detergents promoted twitching like bile salts, stresses applied by antibiotics, including the outer membrane-targeting polymyxin B, did not enhance twitching motility. More importantly, bacteria displayed increased twitching on hydrophilic surfaces such as those of glass and tissue culture-treated polystyrene plastics, and bile salts no longer stimulated twitching on these surfaces. Together, our results show that altering the hydrophilicity of a twitching surface significantly impacts T4P functionality. IMPORTANCEThe bacterial type IV pilus (T4P) is a critical virulence factor for many medically important pathogens, some of which are prioritized by the World Health Organization for their high levels of antibiotic resistance. The T4P is known to propel bacterial twitching motility, the analysis of which provides a convenient assay for T4P functionality. Here, we show that bile salts and other detergents augment the twitching of multiple bacterial pathogens. We identified the underlying mechanism as the alteration of surface hydrophilicity by detergents. Consequently, hydrophilic surfaces like those of glass or plasma-treated polystyrene promote bacterial twitching, bypassing the requirement for detergents. The implication is that surface properties, such as those of tissues and medical implants, significantly impact the functionality of bacterial T4P as a virulence determinant. This offers valuable insights for developing countermeasures against the colonization and infection by bacterial pathogens of critical importance to human health on a global scale. 

Abstract Twitching motility is a form of bacterial surface translocation powered by the type IV pilus (T4P). It is frequently analyzed by interstitial colony expansion between agar and the polystyrene surfaces of Petri dishes. In such assays, the twitching motility of Acinetobacter nosocomialis was observed with MacConkey but not Luria-Bertani (LB) agar media. One difference between these two media is the presence of bile salts as a selective agent in MacConkey but not in LB. Here, we demonstrate that the addition of bile salts to LB allowed A. nosocomialis to display twitching. Similarly, bile salts enhanced the twitching of Acinetobacter baumannii and Pseudomonas aeruginosa in LB. These observations suggest that there is a common mechanism whereby bile salts enhance bacterial twitching and promote interstitial colony expansion. Bile salts disrupt lipid membranes and apply envelope stress as detergents. Surprisingly, their stimulatory effect on twitching appears not to be related to a bacterial physiological response to stressors. Rather it is due to their ability to alter the physicochemical properties of a twitching surface. We observed that while other detergents promoted twitching like bile salts, stresses applied by antibiotics, including the outer membrane-targeting polymyxin B, did not enhanced twitching motility. More importantly, bacteria displayed increased twitching on hydrophilic surfaces such as those of glass and tissue culture-treated polystyrene plastics, and bile salts no longer stimulated twitching on these surfaces. Together, our results show that altering the hydrophilicity of a twitching surface significantly impacts T4P functionality. 

In the k -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger and Stein can solve this in roughly O ( n 2k ) time. However, lower bounds from conjectures about the k -clique problem imply that Ω ( n (1- o (1)) k ) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general k -cut in n 1.98k + O(1) time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights). In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixed k -cut of weight α λ k with probability Ω k ( n - α k ), where λ k denotes the minimum k -cut weight. This also gives an extremal bound of O k ( n k ) on the number of minimum k -cuts and an algorithm to compute λ k with roughly n k polylog( n ) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight k -clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 λ k / k , using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—in the Karger process. 

Unraveling the mechanisms underlying the maintenance of species diversity is a central pursuit in ecology. It has been hypothesized that ectomycorrhizal (EcM) in contrast to arbuscular mycorrhizal fungi can reduce tree species diversity in local communities, which remains to be tested at the global scale. To address this gap, we analyzed global forest inventory data and revealed that the relationship between tree species richness and EcM tree proportion varied along environmental gradients. Specifically, the relationship is more negative at low latitudes and in moist conditions but is unimodal at high latitudes and in arid conditions. The negative association of EcM tree proportion on species diversity at low latitudes and in humid conditions is likely due to more negative plant-soil microbial interactions in these regions. These findings extend our knowledge on the mechanisms shaping global patterns in plant species diversity from a belowground view. 

Anthropogenic disturbances are changing the structure and composition of tropical forests worldwide. Multiple disturbances often occur simultaneously in forests: for example, hunting and logging are within-forest disturbances that impact vast areas of seemingly intact rainforests. Despite recent work on the individual effects of these disturbances, our understanding of how they interact to influence tree communities is still limited. In northern Republic of Congo, we explored the effects of hunting and logging on tree communities. Over an 8-year period, we monitored 12,552 tree stems (≥ 10 cm diameter-at-breast height) spread over 30 1-ha plots along a gradient of human disturbance to compare the tree diversity between hunted and logged forest, once-logged forest, and protected forest free of both disturbances. Tree density, species richness, and community composition were affected by both hunting and logging. Forest close to human settlements was richer, more heterogenous, and more dynamic in species composition across censuses. In hunted and logged forest, fast-growing secondary species with low shade tolerance replaced old growth species. Comparatively, the once-logged forest had the greatest stem density and intermediate species richness with an increased density of shade-bearing species over time. Both tree species spatial turnover and tree recruitment were greatly affected by proximity to human settlements. A shift towards abiotically dispersed trees and increasing seed predation by rodents near villages can partly explain the differences in tree recruitment across the forest types. The combination of hunting and logging seems to have a greater impact on tree communities than either single disturbance, especially with nearness to villages.